The invention is directed to methods and apparata for solving problems of geometric modeling and engineering analysis, wherein the methods and apparata do not require spatial discretization of the underlying geometric domain or its boundary into elements which conform to the geometry (an activity commonly known as xe2x80x9cmeshingxe2x80x9d).
In engineering fields, geometric modeling of objects and the engineering analysis of the behavior of the modeled objects are extremely important activities. Modeling is generally performed by constructing a representation of an object""s geometry on a computer (i.e., a CAD geometric model), with the representation including the xe2x80x9cenvironmentxe2x80x9d of the object (that is, the object""s boundary conditions, such as loads exerted on the object, temperatures on and around the object, and other physical and non-physical functional values). The analysis of the model""s behavior is then usually also performed by computer, with the goal of predicting the modeled object""s physical behavior based on the boundary conditions defined for the geometric model. In general, this involves determining physical functional values and/or their derivatives everywhere in the geometric model, both on its boundaries and in its interiorxe2x80x94these values and derivatives being referred to herein as xe2x80x9cfield valuesxe2x80x9dxe2x80x94based on the known boundary conditions defined at isolated locations on the model. The two activities of modeling and analysis are highly interrelated in that modeling is the prerequisite for analysis, while results of analysis are often used for further modeling. Most geometric models and analysis-related functions are represented in a piecewise fashion, which requires discretization of the model (e.g., construction of a mesh or grid) into finite elements that conform to and approximate the overall model.
However, modeling and analysis have largely emerged as two separate activities that are only weakly connected because they operate on distinct computer representations (e.g., the geometric domain of the model vs. the functional domain of the analysis), and the conversion process between these representations, effected by the aforementioned discretization, is time-consuming and difficult. This results in a slow and inefficient modeling and analysis cycle; the inability to reflect the results of analysis in the original model; difficulty in integrating multiple types of analyses on a common design model, and severely restricted types of analyses available for applications with time-varying geometries. Discretization (i.e., xe2x80x9cmeshingxe2x80x9d) now dominates modeling and analysis activities both in manual effort and computer time. Thus, it is highly desirable to have xe2x80x9cmesh-freexe2x80x9d methods and apparata for modeling and analysis.
One of the main challenges for mesh-free modeling and analysis methods lies in constructing solutions to boundary value problems (e.g., differential equations) wherein the solutions satisfy the prescribed boundary conditions. The classical methods such as FEM (Finite Element Method), BEIM (Boundary Element Integral Methods), and FD (Finite Differences) rely on spatial discretization of the domain and/or its boundary in order to enforce or approximate the imposed boundary conditions at discrete locations. In contrast, the mesh-free methods discretize not the geometric domain but the underlying functional spacexe2x80x94that is, the mathematical domain of the model rather than its physical domain. A number of mesh-free techniques which do not require discretization of the geometry have been developed (see T. Belytschko, Y. Krongauz, D. Organ, M. Fleming and P. Krysl, Meshless methods: An overview and recent developments. Comput. Methods Appl. Mech. Engrg., 139:3-47, 1996): smooth particle hydrodynamics (SPH); the diffuse element method (DEM); the reproducing kernel particle method (RKPM); the HP cloud method; the partition of unity method (PUM), and others. But geometric non-conformance of all such mesh-free methods (i.e., an inexact match between the geometric model and the functional model) makes treatment of boundary conditions problematic. Proposed remedies include the combination of the Element Free Galerkin Method (EFG) with finite element shape functions near the boundary; the use of modified variational principle; window or correction functions that vanish on the boundary; and Lagrange multipliers. Although these techniques appear promising for use in some cases, they often contradict the mesh-free nature of the approximation near the boundary, introduce additional constraints on solutions, or lead to systems with an increased number of unknowns (see, e.g. Frank C. Gunter and Wing Kam Liu, Implementation of boundary conditions for meshless methods. Computer Methods in Applied Mechanics and Engineering, 163:205-230, 1998).
Other mesh-free methods appear promising, but are cumbersome to use. In V. L. Rvachev, Theory of R-functions and Some Applications, Naukova Dumka, 1982 (in Russian), Rvachev developed the theory of R-functionsxe2x80x94real-valued functions that behave as continuous analogs of logical Boolean functions. With R-functions, it became possible to construct functions with prescribed values and derivatives at specified locations, assisting in the solution of boundary value problems. Over the last several decades, the theory of R-functions has matured and has been applied to numerous scientific and engineering problems by Rvachev and his students, including problems of heat transfer, elasticity, magneto-hydrodynamics, various problems in inhomogeneous media, and many other areas. The theory of R-functions was implemented in a software system for scientific programming called POLYE (V. L. Rvachev and G. P. Manko, Automation of Programming for Boundary Value Problems, Naukova Dumka, 1983, in Russian; V. L. Rvachev, G. P. Manko, and A. N. Shevchenko, The R-function approach and software for the analysis of physical and mechanical fields, in J. P. Crestin and J. F. McWaters, editors, Software for Discrete Manufacturing, Paris, 1986, North-Holland). POLYE assists users in solving boundary value problems using a symbolic programming language called RL, in which a user may define a geometric domain, boundary conditions, and a solution structure for a selected problem. However, while POLYE and the RL language simplify the solution of boundary value problems, the problems are still largely manually solved insofar as the user must define the problem, including matters such as identifying and defining implicit functions for the geometry, selection and definition of solution structures, and the selection and definition of a solution procedure. Essentially, the POLYE software serves as an equation solver much like Mathematica (Wolfram Research, Champaign, Ill., USA), MATLAB (MathWorks, Inc., Natick, Mass., USA), or EES (Engineering Equation Solver, F-Chart Software, Middleton, Wis., USA), wherein the user is left to properly define the parameters of the problem and the software is specially configured to process the problem after it is properly defined. Therefore, unless the user has a high degree of knowledge and expertise in defining the problem parameters in the POLYE solver""s language and environment, it is difficult to use. Other manual symbolic methods for construction of solution structures have been further explored in J. Kucwaj and J. Orkisz, Computer approach to the R-function method of solution of boundary value problems in arbitrary domains, Computers and Structures, 22(1):1-12, 1986.
Apart from the manual methods"" need for significant experience and knowledge for their use, these methods also suffer from the significant drawback that they do not easily accommodate preexisting problem data, i.e., they do not allow the direct use of common engineering data such as CAD geometric models. Engineers often perform geometric modeling and problem definition in CAD systems because CAD systems are readily available and easy to use. They also allow the engineer to work in the geometric domain, which is intuitive and easy to comprehend because it approximates one""s physical environment: one can simply draw a geometric representation of a physical object. However, POLYE and similar systems require boundary value problems to be defined in the mathematical domain, and the translation between the geometric and mathematical domains is not trivial. It is extremely time-consuming to construct the equations which define a geometric model, and such construction often requires the application of the user""s expertise and judgement because there may be one or more mathematical analogues available for a geometric model. Further, for some geometries, an exact translation may not be practical or possible.
Owing to the drawbacks of the prior meshing and mesh-free methods, it would be helpful to have available other methods of modeling and solving boundary value problems, particularly if they could be implemented on computers in a highly automated fashion. More specifically, it would be helpful to have available highly automated methods for mesh-free modeling and solution of boundary value problems, so that the problems inherent in meshing methods may be avoided.
The present invention, which is defined by the claims set out at the end of this disclosure, involves methods and apparata capable of integrating geometric modeling and engineering analysis without requiring meshing. A CAD geometric model may be created within the invention (e.g., if the invention is provided as part of a CAD package) or outside the invention (e.g., if the invention is a stand-alone application which may receive output from CAD programs), and is provided with known field values defined on at least one portion of the model. The known field values may be of one or more types, e.g., Dirichlet boundary conditions, Neumann boundary conditions, etc. To determine unknown field values in the model, each portion of the model""s geometry which has known field values is converted to an implicit function which mathematically represents the portion""s geometry. This may be done by resolving each portion of the model into its component geometric primitives whose logical combination defines the portion. Implicit functions may be defined for each primitive, and the implicit functions are then logically combined, preferably by use of R-functions, to obtain the implicit function which mathematically represents the portion""s geometry.
Then, for each type of field value, an interpolating function is constructed from the field values belonging to that type of field value and from the implicit functions representing the portions of the geometry corresponding to that field value. As suggested by its name, the interpolating function interpolates the field values over the model""s geometry, and it does so without the need for meshing. A composite implicit function is also constructed for each type of field value by combining the implicit functions representing the portions of the geometry corresponding to that field value. A solution structure for each type of field value may then be constructed from its interpolating function, its composite implicit function, and from predefined basis functions having unknown coefficients. If more than one type of field value exists, a combined solution structure, which combines the solution structures for the various types of field values, may be constructed by interpolating the solution structures for the different types using the composite implicit functions constructed for the different types. The resulting solution structure may then be processed by a solution procedure to determine the unknown coefficients of the basis functions, as by using one or more of the steps of differentiating, integrating, and/or algebraically solving for unknown coefficients within the solution structure (or portions thereof). Once the unknown coefficients are determined, they may be used to determine not only the field values (physical conditions) at the boundary of the model""s geometry, but also its field values within the boundaries of the model""s geometry. Thus, the invention supports mesh-free analyses of spatially distributed problems without requiring spatial discretization of the geometric domain and boundary conditions.
To summarize the invention in greater detail, a preferred method encompassed by the invention includes the following steps:
Supplying a geometric model to be analyzed;
Constructing implicit functions which mathematically represent the geometry, with these implicit functions taking zero values (or other discrete values) at specified locations on the geometry (as described later in this document in conjunction with Step 110 in FIG. 1);
Supplying the known boundary conditions (e.g., loads, temperatures, displacements, etc.) applicable on the geometric model (as described later in this document in conjunction with Step 120 in FIG. 1);
Utilizing the implicit functions and boundary conditions to construct a data structure for an interpolating function that interpolates the boundary conditions across portions of the geometry (as described later in this document in conjunction with Step 130 in FIG. 1);
Constructing a solution structurexe2x80x94a data structure representing classes of functions satisfying all boundary conditions, either exactly or approximately, on specified locations of the geometryxe2x80x94from the interpolating function, and from basis functions with undetermined coefficients (as also described elsewhere in conjunction with Step 130). The basis functions may or may not be associated with a grid (mesh), but importantly any such mesh does not need to conform to the given geometry;
Solving for the unknown coefficients which allow satisfaction of the differential equation of the problem, either exactly or approximately (as described later in this document in conjunction with Step 140 in FIG. 1);
Utilizing the now-known coefficients in the solution structure, and thereby solving for the field values within and upon the geometric model (as is also discussed in conjunction with Step 140).
In essence, the invention does not require conforming meshing by using special functionsxe2x80x94solution structuresxe2x80x94that can be automatically constructed directly from CAD system inputs (and/or inputs from other applications). The solution process can take advantage of the fact that the constructed solution structures can be automatically differentiated and/or integrated over geometric domains using known procedures. The engineering analysis problem is solved when all unknown coefficients in the solution structure are determined. A typical solution procedure requires differentiation and integration of the constructed functions over the geometric domain, as well as solving a system of algebraic equations. All of these steps may be carried out without meshing, or on a non-conforming mesh/grid (one which need not conform to the geometry).
As described elsewhere in this document, the invention may accommodate highly automated processing of boundary value problems defined on CAD geometric models in a wide variety of formats, including Constructive Solid Geometry (CSG) models, boundary representation (b-rep) models, and feature-based models. To enhance processing speed, the invention need not directly process the CAD geometric model, but may instead process an approximated representation of the CAD geometric model, e.g., a piecewise-smooth or triangulated model, or a similar approximation.
Several significant advantages are attained by the invention""s ability to determine unknown field values without the need to define a geometry-dependent mesh. The arduous task of mesh definition over the geometry is avoided, leading to significant time and labor savings. Additionally, once the unknown field values are determined by the invention, a user may step back and modify/redefine the initially-known field values, and then re-solve for the unknown field values without the need to redefine a mesh on the geometry. The user may alternatively or additionally revise the geometric model and re-solve for the unknown field values, also without the need to redefine a mesh. The invention also allows newly-determined field values to be readily xe2x80x9crecycledxe2x80x9d as known field values, and then used to solve other unknown field values. As an example, in a problem wherein the objective is to determine unknown temperature field valuesxe2x80x94i.e., to determine the temperature field defined about the geometric model, based on some set of initially-defined field valuesxe2x80x94some or all of the values of the newly-determined temperature field might then be used (either alone or in combination with other known field values) to determine the mechanical stress or force field defined on the geometric model. When this is done, there is no need to define or reconfigure a mesh on the geometry to permit accurate solution of the stress/force field values. Alternatively, the newly-determined field values may themselves be utilized as a new geometric model, e.g., the isolines defined on the geometric model for some particular temperature may themselves be used to define the boundaries of a new geometric model. The new geometric model may then be processed by the invention to find further unknown field values, again without the need to redefine a mesh on the new geometry. Further, the invention may even start with undefined model geometry, and utilize desired model geometry characteristics as known field values. The invention can then solve for unknown model geometry field values to thereby define the overall geometry of the model, making the application highly useful in smoothing/fairing applications and other problems of geometric design.
The ability to solve for unknown field values without the use of meshing also makes the invention very useful in conjunction with other methods and apparata for solving for unknown field values, e.g., in finite element or finite difference techniques using meshing. In this instance, the prior mesh-dependent techniques can be used over regions of the geometry which are amenable to solution by use of the prior techniques, and those regions where prior methods are unworkable, inaccurate, or otherwise inappropriate can be utilized as the geometric model in the present invention.
The invention""s ability to avoid meshing also leads to another significant (but subtle) advantage. Meshing requires breaking the geometry into separate elements, and the boundary value problem is then solved on these elements. In effect, the boundary value problem is not solved on the user""s originally-defined geometryxe2x80x94it is solved on an approximation of the geometry. The discretization of the geometry can lead to artifacts which carry over into later stages of the design process. In contrast, the invention maintains and operates on the original user-specified geometry, making its results more readily useful since one does not need to take into account extra information and considerations introduced by the meshing process. The invention may be utilized as a feature within a CAD program, or as an add-on module which may receive output from, and/or provide output to, a CAD program. The invention, as well as its components and the steps/functions they perform, need not be situated in the same computer or other processing unit, and may be distributed over space. As an example, by use of the internet or other networked systems, a geometric model may be created or otherwise provided in one location; may be transmitted to another location for definition of corresponding implicit functions; and may then be transmitted to another location for determination of the unknown field values. This allows separate specialized databases and processing engines located in different areas to cooperatively provide the invention. For example, a CAD designer who does not have the resources and processing capability to accommodate the invention may forward a geometric model and known field values to a website which then implements the invention and forwards the results back to the designer.
Other important advantages of this invention over other known systems for modeling and analysis are that:
The invention can allow automatic construction of implicit functions which mathematically represent the geometry, and thus a user need not have a high degree of proficiency in mathematics and modeling to define a model that the invention can use. Instead, the invention may accommodate geometric models defined by standard applications (such as CAD software), and can automatically translate these models into forms usable by the invention;
The invention allows the construction of interpolating functions for boundary conditions where such boundary conditions are irregularly specified over the geometry;
The invention allows use of these interpolating functions to construct solution structures that no longer depend on any particular geometry-dependent mesh (or other spatial discretization of the geometry);
The invention allows all prescribed boundary conditions to be satisfied exactly (or approximately) on all boundary points;
The invention can allow automatic construction of solution structures satisfying all boundary conditions (exactly or approximately). The preferred embodiment does this by transfinite interpolation of boundary conditions over corresponding portions of the geometry (as represented by implicit functions, most preferably combined using R-functions), but other methods for constructing solution structures may be used;
The invention can eliminate the problematic and time-consuming need to spatially discretize a given geometry (e.g., generate a mesh);
Geometric models, prescribed boundary conditions, problem formulations (solution structures), and solution procedures can be changed easily and repeatedly, because they are no longer made dependent on any particular discretization scheme;
Because there is no mesh, the method significantly simplifies the modeling and solution of engineering analysis problems involving changing/moving geometries, interfaces, and boundary conditions, which are exceedingly difficult to solve with traditional mesh-based methods;
The invention is very useful for problems in optimization of geometric models, because (1) geometry can be changed easily and repeatedly (there is no need to redefine a mesh when the geometry changes), and (2) the computing sensitivity of the solution is greatly decreased because it does not depend on any particular mesh (i.e., the problem of solution inaccuracy owing to an inappropriately-defined mesh is obviated);
The invention significantly simplifies the problem of engineering data exchange and transfer (for example, over the internet), because no new approximations or representations (such as those generated by meshing) need to be created and transmitted during the modeling or solution procedure, a process which would greatly slow data exchange and transfer;
The invention is easy to implement with existing commercial geometric modeling and analysis systems (e.g., standard CAD software packages);
The invention may be used in conjunction with other known solution methods, including those utilizing meshing. For example, the invention may be used to supplement or complement finite element or finite difference methods, the partition of unity method, or other known methods, whether for comparison, refinement, or other purposes.